home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / cc / dist / rtlanal.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-06-19  |  15.5 KB  |  680 lines
  1. /* Analyze RTL for C-Compiler
  2.    Copyright (C) 1987, 1988 Free Software Foundation, Inc.
  3.  
  4. This file is part of GNU CC.
  5.  
  6. GNU CC is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. GNU CC is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with GNU CC; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. #include "config.h"
  22. #include "rtl.h"
  23.  
  24. extern void note_stores ();
  25. static int reg_set_p ();
  26.  
  27. /* Return 1 if the value of X is unstable
  28.    (would be different at a different point in the program).
  29.    The frame pointer, arg pointer, etc. are considered stable
  30.    (within one function) and so is anything marked `unchanging'.  */
  31.  
  32. int
  33. rtx_unstable_p (x)
  34.      rtx x;
  35. {
  36.   register RTX_CODE code = GET_CODE (x);
  37.   register int i;
  38.   register char *fmt;
  39.  
  40.   if (code == MEM)
  41.     return ! RTX_UNCHANGING_P (x);
  42.  
  43.   if (code == QUEUED)
  44.     return 1;
  45.  
  46.   if (code == CONST || code == CONST_INT)
  47.     return 0;
  48.  
  49.   if (code == REG)
  50.     return ! (REGNO (x) == FRAME_POINTER_REGNUM
  51.           || REGNO (x) == ARG_POINTER_REGNUM
  52.           || RTX_UNCHANGING_P (x));
  53.  
  54.   fmt = GET_RTX_FORMAT (code);
  55.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  56.     if (fmt[i] == 'e')
  57.       if (rtx_unstable_p (XEXP (x, i)))
  58.     return 1;
  59.   return 0;
  60. }
  61.  
  62. /* Return 1 if X has a value that can vary even between two
  63.    executions of the program.  0 means X can be compared reliably
  64.    against certain constants or near-constants.
  65.    The frame pointer and the arg pointer are considered constant.  */
  66.  
  67. int
  68. rtx_varies_p (x)
  69.      rtx x;
  70. {
  71.   register RTX_CODE code = GET_CODE (x);
  72.   register int i;
  73.   register char *fmt;
  74.  
  75.   if (code == MEM)
  76.     return 1;
  77.  
  78.   if (code == QUEUED)
  79.     return 1;
  80.  
  81.   if (code == CONST || code == CONST_INT)
  82.     return 0;
  83.  
  84.   if (code == REG)
  85.     return ! (REGNO (x) == FRAME_POINTER_REGNUM
  86.           || REGNO (x) == ARG_POINTER_REGNUM);
  87.  
  88.   fmt = GET_RTX_FORMAT (code);
  89.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  90.     if (fmt[i] == 'e')
  91.       if (rtx_varies_p (XEXP (x, i)))
  92.     return 1;
  93.   return 0;
  94. }
  95.  
  96. /* Return 1 if X refers to a memory location whose address 
  97.    cannot be compared reliably with constant addresses,
  98.    or if X refers to a BLKmode memory object.  */
  99.  
  100. int
  101. rtx_addr_varies_p (x)
  102.      rtx x;
  103. {
  104.   register enum rtx_code code;
  105.   register int i;
  106.   register char *fmt;
  107.  
  108.   if (x == 0)
  109.     return 0;
  110.  
  111.   code = GET_CODE (x);
  112.   if (code == MEM)
  113.     return GET_MODE (x) == BLKmode || rtx_varies_p (XEXP (x, 0));
  114.  
  115.   fmt = GET_RTX_FORMAT (code);
  116.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  117.     if (fmt[i] == 'e')
  118.       if (rtx_addr_varies_p (XEXP (x, i)))
  119.     return 1;
  120.   return 0;
  121. }
  122.  
  123. /* Nonzero if register REG appears somewhere within IN.
  124.    Also works if REG is not a register; in this case it checks
  125.    for a subexpression of IN that is Lisp "equal" to REG.  */
  126.  
  127. int
  128. reg_mentioned_p (reg, in)
  129.      register rtx reg, in;
  130. {
  131.   register char *fmt;
  132.   register int i;
  133.   register enum rtx_code code;
  134.  
  135.   if (in == 0)
  136.     return 0;
  137.  
  138.   if (reg == in)
  139.     return 1;
  140.  
  141.   code = GET_CODE (in);
  142.  
  143.   switch (code)
  144.     {
  145.       /* Compare registers by number.  */
  146.     case REG:
  147.       return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg);
  148.  
  149.       /* These codes have no constituent expressions
  150.      and are unique.  */
  151.     case CC0:
  152.     case PC:
  153.       return 0;
  154.  
  155.     case CONST_INT:
  156.       return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg);
  157.     }
  158.  
  159.   if (GET_CODE (reg) == code && rtx_equal_p (reg, in))
  160.     return 1;
  161.  
  162.   fmt = GET_RTX_FORMAT (code);
  163.  
  164.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  165.     {
  166.       if (fmt[i] == 'E')
  167.     {
  168.       register int j;
  169.       for (j = XVECLEN (in, i) - 1; j >= 0; j--)
  170.         if (reg_mentioned_p (reg, XVECEXP (in, i, j)))
  171.           return 1;
  172.     }
  173.       else if (fmt[i] == 'e'
  174.            && reg_mentioned_p (reg, XEXP (in, i)))
  175.     return 1;
  176.     }
  177.   return 0;
  178. }
  179.  
  180. /* Nonzero if register REG is used in an insn between
  181.    FROM_INSN and TO_INSN (exclusive of those two).  */
  182.  
  183. int
  184. reg_used_between_p (reg, from_insn, to_insn)
  185.      rtx reg, from_insn, to_insn;
  186. {
  187.   register rtx insn;
  188.   register RTX_CODE code;
  189.   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
  190.     if (((code = GET_CODE (insn)) == INSN
  191.      || code == JUMP_INSN || code == CALL_INSN)
  192.     && reg_mentioned_p (reg, PATTERN (insn)))
  193.       return 1;
  194.   return 0;
  195. }
  196.  
  197. /* Nonzero if register REG is set or clobbered in an insn between
  198.    FROM_INSN and TO_INSN (exclusive of those two).
  199.    Does not notice increments, only SET and CLOBBER.  */
  200.  
  201. int
  202. reg_set_between_p (reg, from_insn, to_insn)
  203.      rtx reg, from_insn, to_insn;
  204. {
  205.   register rtx insn;
  206.   register RTX_CODE code;
  207.   for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn))
  208.     if (((code = GET_CODE (insn)) == INSN
  209.      || code == JUMP_INSN || code == CALL_INSN)
  210.     && reg_set_p (reg, PATTERN (insn)))
  211.       return 1;
  212.   return 0;
  213. }
  214.  
  215. /* Internals of reg_set_between_p.  */
  216.  
  217. static rtx reg_set_reg;
  218. static int reg_set_flag;
  219.  
  220. static void
  221. reg_set_p_1 (x)
  222.      rtx x;
  223. {
  224.   if (reg_overlap_mentioned_p (reg_set_reg, x))
  225.     reg_set_flag = 1;
  226. }
  227.  
  228. static int
  229. reg_set_p (reg, insn)
  230.      rtx reg, insn;
  231. {
  232.   reg_set_reg = reg;
  233.   reg_set_flag = 0;
  234.   note_stores (insn, reg_set_p_1);
  235.   return reg_set_flag;
  236. }
  237.  
  238. /* Return nonzero if hard register in range [REGNO, ENDREGNO)
  239.    appears either explicitly or implicitly in X
  240.    other than being stored into.
  241.  
  242.    References contained within the substructure at LOC do not count.
  243.    LOC may be zero, meaning don't ignore anything.  */
  244.  
  245. int
  246. refers_to_regno_p (regno, endregno, x, loc)
  247.      int regno, endregno;
  248.      rtx x;
  249.      rtx *loc;
  250. {
  251.   register int i;
  252.   register RTX_CODE code;
  253.   register char *fmt;
  254.  
  255.  repeat:
  256.   code = GET_CODE (x);
  257.   if (code == REG)
  258.     {
  259.       i = REGNO (x);
  260.       return (endregno > i && regno < i + HARD_REGNO_NREGS (i, GET_MODE (x)));
  261.     }
  262.  
  263.   if (code == SET)
  264.     {
  265.       /* Note setting a SUBREG counts as referring to the REG it is in!  */
  266.       if (GET_CODE (SET_DEST (x)) != REG
  267.       && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))
  268.     return 1;
  269.       if (loc == &SET_SRC (x))
  270.     return 0;
  271.       x = SET_SRC (x);
  272.       goto repeat;
  273.     }
  274.  
  275.   if (code == CLOBBER)
  276.     {
  277.       if (GET_CODE (SET_DEST (x)) != REG
  278.       && refers_to_regno_p (regno, endregno, SET_DEST (x), loc))
  279.     return 1;
  280.       return 0;
  281.     }
  282.  
  283.   /* X does not match, so try its subexpressions.  */
  284.  
  285.   fmt = GET_RTX_FORMAT (code);
  286.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  287.     {
  288.       if (fmt[i] == 'e' && loc != &XEXP (x, i))
  289.     {
  290.       if (i == 0)
  291.         {
  292.           x = XEXP (x, 0);
  293.           goto repeat;
  294.         }
  295.       else
  296.         if (refers_to_regno_p (regno, endregno, XEXP (x, i), loc))
  297.           return 1;
  298.     }
  299.       else if (fmt[i] == 'E')
  300.     {
  301.       register int j;
  302.       for (j = XVECLEN (x, i) - 1; j >=0; j--)
  303.         if (loc != &XVECEXP (x, i, j)
  304.         && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc))
  305.           return 1;
  306.     }
  307.     }
  308.   return 0;
  309. }
  310.  
  311. /* Nonzero if X contains any reg that overlaps hard register REG.  */
  312.  
  313. int
  314. reg_overlap_mentioned_p (reg, x)
  315.      rtx reg, x;
  316. {
  317.   int regno = REGNO (reg);
  318.   int endregno = regno + HARD_REGNO_NREGS (regno, GET_MODE (reg));
  319.   return refers_to_regno_p (regno, endregno, x, 0);
  320. }
  321.  
  322. /* This is 1 until after reload pass.  */
  323. int rtx_equal_function_value_matters;
  324.  
  325. /* Return 1 if X and Y are identical-looking rtx's.
  326.    This is the Lisp function EQUAL for rtx arguments.  */
  327.  
  328. int
  329. rtx_equal_p (x, y)
  330.      rtx x, y;
  331. {
  332.   register int i;
  333.   register int j;
  334.   register enum rtx_code code;
  335.   register char *fmt;
  336.  
  337.   if (x == y)
  338.     return 1;
  339.   if (x == 0 || y == 0)
  340.     return 0;
  341.  
  342.   code = GET_CODE (x);
  343.   /* Rtx's of different codes cannot be equal.  */
  344.   if (code != GET_CODE (y))
  345.     return 0;
  346.  
  347.   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.
  348.      (REG:SI x) and (REG:HI x) are NOT equivalent.  */
  349.  
  350.   if (GET_MODE (x) != GET_MODE (y))
  351.     return 0;
  352.  
  353.   /* These three types of rtx's can be compared nonrecursively.  */
  354.   /* Until the end of reload,
  355.      don't consider the a reference to the return register of the current
  356.      function the same as the return from a called function.  This eases
  357.      the job of function integration.  Once the distinction no longer
  358.      matters, the insn will be deleted.  */
  359.   if (code == REG)
  360.     return (REGNO (x) == REGNO (y)
  361.         && (! rtx_equal_function_value_matters
  362.         || REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)));
  363.   if (code == LABEL_REF)
  364.     return XEXP (x, 0) == XEXP (y, 0);
  365.   if (code == SYMBOL_REF)
  366.     return XSTR (x, 0) == XSTR (y, 0);
  367.  
  368.   /* Compare the elements.  If any pair of corresponding elements
  369.      fail to match, return 0 for the whole things.  */
  370.  
  371.   fmt = GET_RTX_FORMAT (code);
  372.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  373.     {
  374.       switch (fmt[i])
  375.     {
  376.     case 'i':
  377.       if (XINT (x, i) != XINT (y, i))
  378.         return 0;
  379.       break;
  380.  
  381.     case 'E':
  382.       /* Two vectors must have the same length.  */
  383.       if (XVECLEN (x, i) != XVECLEN (y, i))
  384.         return 0;
  385.  
  386.       /* And the corresponding elements must match.  */
  387.       for (j = 0; j < XVECLEN (x, i); j++)
  388.         if (rtx_equal_p (XVECEXP (x, i, j), XVECEXP (y, i, j)) == 0)
  389.           return 0;
  390.       break;
  391.  
  392.     case 'e':
  393.       if (rtx_equal_p (XEXP (x, i), XEXP (y, i)) == 0)
  394.         return 0;
  395.       break;
  396.  
  397.     case 's':
  398.       if (strcmp (XSTR (x, i), XSTR (y, i)))
  399.         return 0;
  400.       break;
  401.  
  402.     case 'u':
  403.       /* These are just backpointers, so they don't matter.  */
  404.       break;
  405.  
  406.     case '0':
  407.       break;
  408.  
  409.       /* It is believed that rtx's at this level will never
  410.          contain anything but integers and other rtx's,
  411.          except for within LABEL_REFs and SYMBOL_REFs.  */
  412.     default:
  413.       abort ();
  414.     }
  415.     }
  416.   return 1;
  417. }
  418.  
  419. /* Call FUN on each register or MEM that is stored into or clobbered by X.
  420.    (X would be the pattern of an insn).
  421.    FUN receives two arguments:
  422.      the REG, MEM, CC0 or PC being stored in or clobbered,
  423.      the SET or CLOBBER rtx that does the store.  */
  424.      
  425. void
  426. note_stores (x, fun)
  427.      register rtx x;
  428.      void (*fun) ();
  429. {
  430.   if ((GET_CODE (x) == SET || GET_CODE (x) == CLOBBER))
  431.     {
  432.       register rtx dest = SET_DEST (x);
  433.       while (GET_CODE (dest) == SUBREG
  434.          || GET_CODE (dest) == ZERO_EXTRACT
  435.          || GET_CODE (dest) == SIGN_EXTRACT
  436.          || GET_CODE (dest) == STRICT_LOW_PART)
  437.     dest = XEXP (dest, 0);
  438.       (*fun) (dest, x);
  439.     }
  440.   else if (GET_CODE (x) == PARALLEL)
  441.     {
  442.       register int i;
  443.       for (i = XVECLEN (x, 0) - 1; i >= 0; i--)
  444.     {
  445.       register rtx y = XVECEXP (x, 0, i);
  446.       if (GET_CODE (y) == SET || GET_CODE (y) == CLOBBER)
  447.         {
  448.           register rtx dest = SET_DEST (y);
  449.           while (GET_CODE (dest) == SUBREG
  450.              || GET_CODE (dest) == ZERO_EXTRACT
  451.              || GET_CODE (dest) == SIGN_EXTRACT
  452.              || GET_CODE (dest) == STRICT_LOW_PART)
  453.         dest = XEXP (dest, 0);
  454.           (*fun) (dest, XVECEXP (x, 0, i));
  455.         }
  456.     }
  457.     }
  458. }
  459.  
  460. /* Return nonzero if register REG's old contents don't survive after INSN.
  461.    This can be because REG dies in INSN or because INSN entirely sets REG.
  462.  
  463.    "Entirely set" means set directly and not through a SUBREG,
  464.    ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains.
  465.  
  466.    REG may be a hard or pseudo reg.  Renumbering is not taken into account,
  467.    but for this use that makes no difference, since regs don't overlap
  468.    during their lifetimes.  Therefore, this function may be used
  469.    at any time after deaths have been computed (in flow.c).  */
  470.  
  471. int
  472. dead_or_set_p (insn, reg)
  473.      rtx insn;
  474.      rtx reg;
  475. {
  476.   register rtx link;
  477.   register int regno = REGNO (reg);
  478.  
  479.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  480.     if ((REG_NOTE_KIND (link) == REG_DEAD
  481.      || REG_NOTE_KIND (link) == REG_INC)
  482.     && REGNO (XEXP (link, 0)) == regno)
  483.       return 1;
  484.  
  485.   if (GET_CODE (PATTERN (insn)) == SET)
  486.     return SET_DEST (PATTERN (insn)) == reg;
  487.   else if (GET_CODE (PATTERN (insn)) == PARALLEL)
  488.     {
  489.       register int i;
  490.       for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
  491.     {
  492.       if (GET_CODE (XVECEXP (PATTERN (insn), 0, i)) == SET
  493.           && SET_DEST (XVECEXP (PATTERN (insn), 0, i)) == reg)
  494.         return 1;
  495.     }
  496.     }
  497.   return 0;
  498. }
  499.  
  500. /* Return the reg-note of kind KIND in insn INSN, if there is one.
  501.    If DATUM is nonzero, look for one whose datum is DATUM.  */
  502.  
  503. rtx
  504. find_reg_note (insn, kind, datum)
  505.      rtx insn;
  506.      enum reg_note kind;
  507.      rtx datum;
  508. {
  509.   register rtx link;
  510.  
  511.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  512.     if (REG_NOTE_KIND (link) == kind
  513.     && (datum == 0 || datum == XEXP (link, 0)))
  514.       return link;
  515.   return 0;
  516. }
  517.  
  518. /* Return the reg-note of kind KIND in insn INSN which applies to register
  519.    number REGNO, if any.  Return 0 if there is no such reg-note.  */
  520.  
  521. rtx
  522. find_regno_note (insn, kind, regno)
  523.      rtx insn;
  524.      enum reg_note kind;
  525.      int regno;
  526. {
  527.   register rtx link;
  528.  
  529.   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
  530.     if (REG_NOTE_KIND (link) == kind
  531.     && REGNO (XEXP (link, 0)) == regno)
  532.       return link;
  533.   return 0;
  534. }
  535.  
  536. /* Nonzero if FROM precedes TO with no intervening labels.  */
  537.  
  538. int
  539. no_labels_between (from, to)
  540.      register rtx from, to;
  541. {
  542.   register rtx p = to;
  543.  
  544.   while (1)
  545.     {
  546.       p = PREV_INSN (p);
  547.       if (p == 0)
  548.     return 0;
  549.       if (p == from)
  550.     return 1;
  551.       if (GET_CODE (p) == CODE_LABEL)
  552.     return 0;
  553.     }
  554. }
  555.  
  556. /* Nonzero if X contains any volatile memory references
  557.    or volatile ASM_OPERANDS expressions.  */
  558.  
  559. int
  560. volatile_refs_p (x)
  561.      rtx x;
  562. {
  563.   register RTX_CODE code;
  564.  
  565.   code = GET_CODE (x);
  566.   switch (code)
  567.     {
  568.     case LABEL_REF:
  569.     case SYMBOL_REF:
  570.     case CONST_INT:
  571.     case CONST:
  572.     case CONST_DOUBLE:
  573.     case CC0:
  574.     case PC:
  575.     case REG:
  576.     case CLOBBER:
  577.     case ASM_INPUT:
  578.     case ADDR_VEC:
  579.     case ADDR_DIFF_VEC:
  580.       return 0;
  581.  
  582.     case CALL:
  583.       return 1;
  584.  
  585.     case MEM:
  586.     case ASM_OPERANDS:
  587.       if (MEM_VOLATILE_P (x))
  588.     return 1;
  589.     }
  590.  
  591.   /* Recursively scan the operands of this expression.  */
  592.  
  593.   {
  594.     register char *fmt = GET_RTX_FORMAT (code);
  595.     register int i;
  596.     
  597.     for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  598.       {
  599.     if (fmt[i] == 'e')
  600.       {
  601.         if (volatile_refs_p (XEXP (x, i)))
  602.           return 1;
  603.       }
  604.     if (fmt[i] == 'E')
  605.       {
  606.         register int j;
  607.         for (j = 0; j < XVECLEN (x, i); j++)
  608.           if (volatile_refs_p (XVECEXP (x, i, j)))
  609.         return 1;
  610.       }
  611.       }
  612.   }
  613.   return 0;
  614. }
  615.  
  616. /* Return nonzero if evaluating rtx X might cause a trap.  */
  617.  
  618. int
  619. may_trap_p (x)
  620.      rtx x;
  621. {
  622.   int i;
  623.   enum rtx_code code;
  624.   char *fmt;
  625.  
  626.   if (x == 0)
  627.     return 0;
  628.   code = GET_CODE (x);
  629.   switch (code)
  630.     {
  631.       /* Handle these cases fast.  */
  632.     case CONST_INT:
  633.     case CONST_DOUBLE:
  634.     case SYMBOL_REF:
  635.     case LABEL_REF:
  636.     case CONST:
  637.     case PC:
  638.     case CC0:
  639.     case REG:
  640.       return 0;
  641.  
  642.       /* Memory ref can trap unless it's a static var or a stack slot.  */
  643.     case MEM:
  644.       return rtx_varies_p (XEXP (x, 0));
  645.  
  646.       /* Division by a non-constant might trap.  */
  647.     case DIV:
  648.     case MOD:
  649.     case UDIV:
  650.     case UMOD:
  651.       if (! CONSTANT_P (XEXP (x, 1))
  652.       && GET_CODE (XEXP (x, 1)) != CONST_DOUBLE)
  653.     return 1;
  654.       if (XEXP (x, 1) == const0_rtx)
  655.     return 1;
  656.     default:
  657.       /* Any floating arithmetic may trap.  */
  658.       if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT)
  659.     return 1;
  660.     }
  661.  
  662.   fmt = GET_RTX_FORMAT (code);
  663.   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
  664.     {
  665.       if (fmt[i] == 'e')
  666.     {
  667.       if (may_trap_p (XEXP (x, i)))
  668.         return 1;
  669.     }
  670.       else if (fmt[i] == 'E')
  671.     {
  672.       register int j;
  673.       for (j = 0; j < XVECLEN (x, i); j++)
  674.         if (may_trap_p (XVECEXP (x, i, j)))
  675.           return 1;
  676.     }
  677.     }
  678.   return 0;
  679. }
  680.